package my;

import java.util.Arrays;

/**
 * 贪心 - 零钱兑换
 *
 * @author AJun
 * @date 2020/11/25
 */
public class CoinChange {

    public static void main(String[] args) {
        CoinChange cc = new CoinChange();
        Integer[] faces = {25, 5, 10, 1};
        int money = 41;
        System.out.println("找给客户的硬币数量: " + cc.coinChange1(faces, money));
        System.out.println("找给客户的硬币数量: " + cc.coinChange2(faces, money));
        System.out.println("找给客户的硬币数量: " + cc.coinChange(faces, money));
    }

    public int coinChange(Integer[] faces, int money) {
        Arrays.sort(faces);

        int coins = 0;
        int i = faces.length - 1;
        while (i >= 0) {
            while (money >= faces[i]) {
                System.out.println(faces[i]);
                money -= faces[i];
                coins++;
            }
            i--;
        }
        return coins;
    }

    public int coinChange2(Integer[] faces, int money) {
        Arrays.sort(faces, (f1, f2) -> f2 - f1);

        int coins = 0;
        int i = 0;
        while (i < faces.length) {
            if (money < faces[i]) {
                i++;
                continue;
            }

            System.out.println(faces[i]);
            money -= faces[i];
            coins++;
        }
        return coins;
    }

    public int coinChange1(Integer[] faces, int money) {
        Arrays.sort(faces);

        int coins = 0;
        for (int i = faces.length - 1; i >= 0; i--) {
            if (money < faces[i]) {
                continue;
            }

            System.out.println(faces[i]);
            money -= faces[i];
            coins++;
            i = faces.length;
        }
        return coins;
    }

}
